7/11
team virtual participation
实现一场训练 0 罚时
训练四小时自闭两个小时二十分钟….
题目链接
A
签到
B
题意
二维平面内,给出n个点和m个平行坐标轴的矩形,问每个点被多少个矩形所包含(边界不算)。
(n,m≤105)
题解
树状数组是单点更新区间查询 ! ! !
- 扫描线,离散化y坐标,对x坐标排序。
- 然后依次从小到大处理x,每一个x对应的y在线段树/树状数组更新即可。
C
模拟即可
D
题意
题解
E
题解
给两个凸多边形,问一个是否能包住另一个
题意
- 凸包模板题
- 两个点集的凸包如果是一个多边形的点即可。
- 注意对于在凸包上共线的点也要算入凸包的集合中。
F
- 因为是二叉树,暴力记录每个节点所在子树每层的和即可。
G
- 定义:dp[i][j]表示长度为 i 以 j 结束的最小花费。
- 转移:暴力转移即可。
- 时间复杂度 O(k·262)
H
题意
题解
I
题意
题解
J
签到